1. Field of the Invention
This invention relates to content addressable memory cells and, more particularly, to a content addressable memory cell which can store a state representing "Don't Care".
2. Description of the Related Art
Content addressable memories (CAMs) compare a search word with a set of stored words. An indication of whether or not the search word matches the stored words is produced for each stored word. A distinguishing characteristic of a CAM is that each stored word is uniquely identified on the basis of the content of the word itself, rather than by its address within the memory array as in conventional digital memories.
A CAM includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory elements constitute a stored word. During a match operation, a search word of input data is applied to all the rows, and an indication is produced for each row as to whether or not the search word matches the word stored therein.
Referring now to FIG. 1, there is shown a conventional CAM cell with match logic, according to the prior art. Each CAM cell stores one bit of data within a stored word. In the CAM cell, a storage cell 101 comprises two inverters 101a and 101b connected to form a flip-flop. FIG. 2 shows a typical implementation of the flip-flop using two n-type transistors 201b and 201d, and two p-type transistors 201a and 201c.
The flip-flop has two states: In one state the signal "a" is high, and in the other state it is low. The signal "b" is always the complement of "a". Bit lines BL and BL are connected to the storage cell 101 via access gates, here shown as transistors 103 and 104. A word line designated as W is connected to the gate terminal of each access transistor, and extends out to other cells in the same word row. Match logic 102 is connected to the storage cell and to the bit lines. This match logic has an output designated as MV, which indicates the presence of a match.
The operation of the conventional CAM of FIG. 1 will now be described. Bit lines BL and BL have two functions: a read/write function and a match function. To perform a read/write function, the word line W is used to activate the access transistors 103 and 104. Thus, an electrical connection is made between the bit lines BL and BL and the two terminals of the storage cell 101. Once this connection has been established, the bit lines can either read the state of the storage cell, or write a state onto the cell.
When the access transistors 103 and 104 are deactivated, the storage cell 101 is isolated from BL and BL. In this situation, BL and BL can be used for their match function. A state is asserted on one of the bit lines, and its complement is asserted on the other bit line. If the state of BL matches the state of signal "a", the MV signal will float; if there is no match, MV will be pulled low. For example, suppose we wish to check if "a" is high. A high signal is placed on the BL line and a low signal placed on BL. If "a" is high, transistor 102b will be on, transistor 102a will be off (because BL is low), transistor 102d will be off (because "b" is low), and transistor 102c will be off (because its source terminal is floating). Thus, MV will float, indicating a match. If "a" is low, transistors 102b and 102a will be off, and transistors 102d and 102c will be on (because both BL and "b" are high). Thus, MV will be pulled low, indicating no match.
It can therefore be seen that, when access transistors 103 and 104 are off and the storage cell 101 is isolated from the bit lines, the match logic 102 can be used to check for matches between the bit lines and the data stored in the cell.
When searching for matches in a CAM, it is known in the art to specify "Don't Care" in one or more bits of the search word. Specifying "Don't Care" means that the CAM cell should signal a match regardless of the state of its stored bit. One technique for specifying "Don't Care" in the search word is to pull both BL and BL low. Following the match logic shown in FIG. 1, it can be seen that this would result in MV floating (indicating a match) regardless of the state of the flip-flop.
The technique of specifying "Don't Care" in the search word is useful for searching for ranges of words. For example, to search for all words falling within the range 1011000 to 1011111, one might specify the search word 1011XXX (where "X" represents "Don't Care"). This search word would match with any word falling within the range. This technique can generally be used only on continuous ranges of words; discontinuous ranges require multiple search words.
The technique of specifying "Don't Care" in the search word is to be distinguished from specifying "Don't Care" in the stored data. When "Don't Care" is specified in the search word, a storage cell will indicate a match regardless of the state of its stored bit. On the other hand, when "Don't Care" is stored in the stored data, the cell will indicate a match regardless of the state of the match data. Although it is known in the art to specify "Don't Care" in the match data, conventional CAM design does not have the capability to specify "Don't Care" in the stored data. This technique is useful in applications where multiple discontinuous ranges of words are to be specified.